// 二叉树搜索树转换成排序双向链表


struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x)
        :val(x)
        ,left(nullptr)
        ,right(nullptr)
    {}
};
class Solution 
{
public:
    void InOrderConvert(TreeNode* cur, TreeNode*& prev)// prev不适用引用的话，链接不到cur节点
    {
        if(nullptr == cur) return;

        InOrderConvert(cur->left, prev);
        // 中序
        cur->left = prev;
        if(prev) prev->right = cur;

        prev = cur;

        InOrderConvert(cur->right, prev);
    }
    TreeNode* Convert(TreeNode* pRootOfTree) 
    {
        TreeNode* cur = pRootOfTree, *prev = nullptr;
        InOrderConvert(cur, prev);

        TreeNode* head = pRootOfTree;
        while(head && head->left)
        {
            head = head->left;
        }

        return head;
    }
};